package com.algorithm.code.hash;

import java.util.Objects;

/**
 * 自己实现hash表
 * 1. hash
 * 2. 链地址法
 * 3. Key == null 时，不允许
 *
 * @program: study
 * @className: HashTable
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-01-16 14:38
 * @version: v1.0
 **/
public class HashTable<K, V> {
    /**
     * 最大容量
     */
    private final static int MAX_CAPACITY = 1 << 30;
    /**
     * 初始容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 2; // aka 16
    /**
     * 负载因子
     */
    private final static float LOAD_FACTOR = 0.75f;

    /**
     * 散列表
     */
    private Entry<K, V>[] table;

    /**
     * 实际大小
     */
    private int size = 0;
    /**
     * 使用量
     */
    private int used = 0;

    /**
     * 功能描述: 构造函数
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:07 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:07 下午
     **/
    public HashTable() {
        this.table = new Entry[DEFAULT_INITIAL_CAPACITY];
    }

    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>();

        for (int i = 0; i < 20; ++i) {
            hashTable.put("i:" + i, i);
        }

        hashTable.remove("i:8");
        System.out.println(hashTable.get("i:8"));

    }

    /**
     * 功能描述: 添加元素
     * 散列表结构
     * +-----+
     * |dummy|-->|node1|-->|node2|-->null
     * +-----+
     * |dummy|-->|node3|-->null
     * +-----+
     * |dummy|
     * +-----+
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:08 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:08 下午
     **/
    public void put(K key, V value) {

        if (key == null) {
            return;
        }

        int index = this.hash(key);

        /**
         * 如果元素为空
         * 写入哨兵节点:其为伪节点
         */
        if (Objects.isNull(this.table[index])) {
            this.table[index] = new Entry<>(null, null, null);
        }

        /**
         * 获取槽位上的伪节点
         */
        Entry<K, V> dummy = this.table[index];
        /**
         * 新增节点
         * 采用头插法
         */
        if (Objects.isNull(dummy.next)) {
            dummy.next = new Entry<>(key, value, null);
            ++size;
            ++used;
            /**
             * 动态扩容
             */
            if (used > LOAD_FACTOR * table.length) {
                //todo
                this.resize();
            }
        } else {
            /**
             * 从真正的数据节点开始更新
             * 相同的key更新value
             */
            Entry<K, V> node = dummy.next;
            while (node.next != null) {
                if (node.key.equals(key)) {
                    node.value = value;
                    return;
                }
            }

            /**
             * 不同的key映射到同一个槽位
             * 如果没有相同的元素，则插入一个节点）
             */
            Entry<K, V> next = this.table[index].next;
            this.table[index].next = new Entry<>(key, value, next);
            ++size;
        }
    }

    /**
     * 根据key获取value
     *
     * @param key
     * @return
     */
    public V get(K key) {
        if (Objects.isNull(key)) {
            return null;
        }

        int index = this.hash(key);
        Entry<K, V> dummy = this.table[index];
        /**
         * 如果槽位为空或者是真实节点值为空
         */
        if (dummy == null || dummy.next == null) {
            return null;
        }

        while (dummy.next != null) {
            dummy = dummy.next;
            if (dummy.key.equals(key)) {
                return dummy.value;
            }
        }
        return null;
    }

    /**
     * 功能描述: 移除指定的key
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:45 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:45 下午
     **/
    public void remove(K key) {

        if (key == null) {
            return;
        }

        int index = this.hash(key);

        Entry<K, V> dummy = this.table[index];
        if (dummy == null || dummy.next == null) {
            return;
        }

        Entry<K, V> pre = dummy;
        Entry<K, V> node = dummy.next;

        while (node != null) {
            if (node.key.equals(key)) {
                size--;
                pre.next = node.next;
                node = null;
                /**
                 * 如果伪头节点的后继为空，则删除该节点
                 */
                if (this.table[index].next == null) {
                    used--;
                }
                return;
            }

            pre = node;
            node = node.next;
        }
    }

    /**
     * 功能描述: 动态扩容
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:59 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:59 下午
     **/
    private final void resize() {

        Entry<K, V>[] oldTable = this.table;
        this.table = new Entry[2 * this.table.length];

        this.used = 0;

        for (int i = 0; i < oldTable.length; ++i) {
            if (oldTable[i] == null || oldTable[i].next == null) {
                continue;
            }

            Entry<K, V> e = oldTable[i];
            while (e.next != null) {
                e = e.next;
                int index = this.hash(e.key);

                if (this.table[index] == null) {
                    this.used++;
                    this.table[index] = new Entry<K, V>(null, null, null);
                }

                this.table[index].next = new Entry<>(e.key, e.value, this.table[index].next);
            }
        }
    }

    /**
     * 功能描述: 散列函数
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:10 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:10 下午
     **/
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;
    }

    /**
     * 功能描述: 节点类
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 3:00 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 3:00 下午
     **/
    final static class Entry<K, V> {
        final K key;
        V value;
        /**
         * 下一个节点
         */
        Entry<K, V> next;

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}
